// https://leetcode.cn/problems/profitable-schemes/

// 算法思路总结：
// 1. 动态规划解决盈利计划问题（二维费用背包计数）
// 2. 状态定义：dp[j][k]表示使用j名成员产生至少k利润的方案数
// 3. 双重约束：成员数限制n，利润目标m
// 4. 状态转移：dp[j][k] += dp[j-group][max(0,k-profit)]
// 5. 倒序遍历避免重复计数（0-1背包）
// 6. 时间复杂度：O(w×n×m)，空间复杂度：O(n×m)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    typedef long long ll;
    int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) 
    {
        int w = group.size();

        vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
        for (int j = 0 ; j <= n ; j++)
        {
            dp[j][0] = 1;
        }

        for (int i = 1 ; i <= w ; i++)
        {
            for (int j = n ; j >= group[i - 1] ; j--)
            {
                for (int k = m ; k >= 0 ; k--)
                {                    
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])]; 
                    dp[j][k] %= (ll)1e9 + 7;
                }
            }
        }

        return dp[n][m];
    }
};

int main()
{
    int n1 = 5, n2 = 10;
    int m1 = 3, m2 = 5;
    vector<int> group1 = {2, 2}, group2 = {2, 3, 5};
    vector<int> profit1 = {2, 3}, profit2 = {6,7,8};

    Solution sol;

    cout << sol.profitableSchemes(n1, m1, group1, profit1) << endl;
    cout << sol.profitableSchemes(n2, m2, group2, profit2) << endl;

    return 0;
}